Comparing Monte Carlo methods for finding ground states of Ising spin glasses: population annealing, simulated annealing and parallel tempering

摘要

Population annealing is a Monte Carlo algorithm that marries features fromsimulated annealing and parallel tempering Monte Carlo. As such, it is ideal toovercome large energy barriers in the free-energy landscape while minimizing aHamiltonian. Thus, population annealing Monte Carlo can be used as a heuristicto solve combinatorial optimization problems. We illustrate the capabilities ofpopulation annealing Monte Carlo by computing ground states of thethree-dimensional Ising spin glass with Gaussian disorder, whilst comparing tosimulated annealing and parallel tempering Monte Carlo. Our results suggestthat population annealing Monte Carlo is significantly more efficient thansimulated annealing but comparable to parallel tempering Monte Carlo forfinding spin-glass ground states.